package com.leetcode.partition13;

import java.util.HashMap;
import java.util.Map;

/**
 * @author `RKC`
 * @date 2021/11/5 8:57
 */
public class LC1218最长定差子序列 {

    public static int longestSubsequence(int[] arr, int difference) {
        return hashtable(arr, difference);
    }

    public static void main(String[] args) {
        int[] arr = {3, 4, -3, -2, -4};
        System.out.println(longestSubsequence(arr, -5));
    }

    private static int hashtable(int[] arr, int difference) {
        Map<Integer, Integer> differenceTable = new HashMap<>();
        for (int num : arr) {
            //总是希望查找左边等差的元素
            if (differenceTable.containsKey(num - difference)) {
                differenceTable.put(num, differenceTable.get(num - difference) + 1);
            } else {
                differenceTable.put(num, 1);
            }
        }
        System.out.println(differenceTable);
        return differenceTable.values().stream().max(Integer::compare).get();
    }

    private static int dynamicProgramming(int[] arr, int difference) {
        //dp[i]代表子数组arr[0, i]之间的最长定差子序列
        int[] dp = new int[arr.length];
        int answer = 1;
        for (int i = 1; i < arr.length; i++) {
            for (int j = 0; j < i; j++) {
                //和最长递增子序列递推公式一样，条件是要两个元素形成差，且第一次形成的差值代表有两个元素，赋初值2
                if (arr[i] - arr[j] == difference) {
                    dp[i] = dp[j] == 0 ? 2 : Math.max(dp[i], dp[j] + 1);
                }
            }
            answer = Math.max(answer, dp[i]);
        }
        return answer;
    }
}
